{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "raw_mimetype": "text/restructuredtext"
   },
   "source": [
    ".. _nb_perm:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "raw_mimetype": "text/restructuredtext"
   },
   "source": [
    "# Permutations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Permutations are a very particular type where each integer value occurs only once. Your algorithm to solve your optimization problem efficiently might need some customization regarding the evolutionary operators. \n",
    "\n",
    "In the following, two examples of permutation problems shall be provided."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Traveling Salesman Problem (TSP)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The traditional traveling salesman problem aims to minimize the time to travel to visit each city exactly once. \n",
    "Since a permutation can start with an arbitrary number, it is advisable to avoid oranges with apples and to repair each individual to start with the index `0`. Therefore, let us define a `Repair` operator as follows: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "from pymoo.core.repair import Repair\n",
    "\n",
    "class StartFromZeroRepair(Repair):\n",
    "\n",
    "    def _do(self, problem, X, **kwargs):\n",
    "        I = np.where(X == 0)[1]\n",
    "\n",
    "        for k in range(len(X)):\n",
    "            i = I[k]\n",
    "            X[k] = np.concatenate([X[k, i:], X[k, :i]])\n",
    "\n",
    "        return X"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For permutations, the corresponding operators need to be supplied to the `GA` constructor. Here, we choose random permutations, edge recombination crossover, and inversion mutation. Also, the repair defined above is provided.\n",
    "The termination is defined to consider the improvement of the last 200 generations. If the improvement is above a tolerance value (default: `f_tol=1e-6`), the algorithm is considered as terminated."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from pymoo.algorithms.soo.nonconvex.ga import GA\n",
    "from pymoo.optimize import minimize\n",
    "from pymoo.problems.single.traveling_salesman import create_random_tsp_problem\n",
    "from pymoo.operators.sampling.rnd import PermutationRandomSampling\n",
    "from pymoo.operators.crossover.ox import OrderCrossover\n",
    "from pymoo.operators.mutation.inversion import InversionMutation\n",
    "from pymoo.termination.default import DefaultSingleObjectiveTermination\n",
    "\n",
    "problem = create_random_tsp_problem(30, 100, seed=1)\n",
    "\n",
    "algorithm = GA(\n",
    "    pop_size=20,\n",
    "    sampling=PermutationRandomSampling(),\n",
    "    mutation=InversionMutation(),\n",
    "    crossover=OrderCrossover(),\n",
    "    repair=StartFromZeroRepair(),\n",
    "    eliminate_duplicates=True\n",
    ")\n",
    "\n",
    "# if the algorithm did not improve the last 200 generations then it will terminate (and disable the max generations)\n",
    "termination = DefaultSingleObjectiveTermination(period=200, n_max_gen=np.inf)\n",
    "\n",
    "res = minimize(\n",
    "    problem,\n",
    "    algorithm,\n",
    "    termination,\n",
    "    seed=1,\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "print(\"Traveling Time:\", np.round(res.F[0], 3))\n",
    "print(\"Function Evaluations:\", res.algorithm.evaluator.n_eval)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from pymoo.problems.single.traveling_salesman import visualize\n",
    "visualize(problem, res.X)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Flowshop Schedule"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This problem is purely optimizing the permutations, and the initial value is not of importance."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from pymoo.problems.single.flowshop_scheduling import create_random_flowshop_problem\n",
    "\n",
    "\n",
    "problem = create_random_flowshop_problem(n_machines=5, n_jobs=10, seed=1)\n",
    "\n",
    "algorithm = GA(\n",
    "    pop_size=20,\n",
    "    eliminate_duplicates=True,\n",
    "    sampling=PermutationRandomSampling(),\n",
    "    mutation=InversionMutation(),\n",
    "    crossover=OrderCrossover()\n",
    ")\n",
    "\n",
    "termination = DefaultSingleObjectiveTermination(period=50, n_max_gen=10000)\n",
    "\n",
    "\n",
    "res = minimize(\n",
    "    problem,\n",
    "    algorithm,\n",
    "    termination,\n",
    "    seed=1\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "print(\"Maximum Span:\", np.round(res.F[0], 3))\n",
    "print(\"Function Evaluations:\", res.algorithm.evaluator.n_eval)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "tags": []
   },
   "outputs": [],
   "source": [
    "from pymoo.problems.single.flowshop_scheduling import visualize\n",
    "visualize(problem, res.X)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<sub>This implementation is based on a contribution made by [Peng-YM](https://github.com/Peng-YM).</sub>"
   ]
  }
 ],
 "metadata": {
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
